import random
import sys


sys.setrecursionlimit(5000)

WALL = 0
WAY = 1
START = 2
AIM = 3

WIDTH = 20
HEIGHT = 20

START_RANDOM = "start at random field"
START_BORDER = "start at border field"

class Basefield:
    def __init__(self, maze, x, y):
        self.x = x
        self.y = y
        self.maze = maze
        self.type = WALL
        self.waylength = -1
        self.wayable = True
    
    def get_neighbors(self):
        return [i for i in [self.maze.get_field(self.x + 1, self.y),
                            self.maze.get_field(self.x - 1, self.y),
                            self.maze.get_field(self.x, self.y + 1),
                            self.maze.get_field(self.x, self.y - 1)]if i]
    
    def get_neighbors_all(self):
        return self.get_neighbors() + \
            [i for i in [self.maze.get_field(self.x + 1, self.y + 1),
                         self.maze.get_field(self.x - 1, self.y - 1),
                         self.maze.get_field(self.x - 1, self.y + 1),
                         self.maze.get_field(self.x + 1, self.y - 1)]if i]
        
    def add_walls(self):
        neighbors = self.get_neighbors()
        for i in neighbors:
            self.maze.walls.append((self, i))
    
    def check_field(self, parent):
        if self.type != WALL: return False
        for i in self.get_neighbors_all():
            if i.type:
                if not (i == parent or parent.x == i.x != self.x
                        or parent.y == i.y != self.y):
                    return False
        return True


class Maze:
    def __init__(self, width, height, field):
        self.fields = [[field(self, i, j) for j in range(0, height)]
                        for i in range(0, width)]
        self.width = width
        self.height = height
        self.diagonal_walls =  None
    
    def get_field(self, x, y):
        if self.width > x >= 0 and self.height > y >= 0:
            return self.fields[x][y]
    
    def start_field(self, position):
        if not isinstance(position, (tuple, list)):
            if position == START_RANDOM:
                start = random.choice(random.choice(self.fields))
            elif position == START_BORDER:
                start = random.choice(list(set(self.fields[0] + \
                                          self.fields[-1] + \
                                          [i[0] for i in self.fields] + \
                                          [i[-1] for i in self.fields])))
            else:
                raise AttributeError("Invalid startposition given!")
        else:
            start = self.get_field(*position)
        start.waylength = 0
        start.type = START
        self.start = start
        return start
            
    def generate_maze_dfs_mod(self, start_pos):
        self.generate_maze_dfs(start_pos, True)
    
    def generate_maze_dfs(self, start_pos, diagonal=False):
        self.diagonal_walls = diagonal
        dfs_fields = [self.start_field(start_pos)]
        while dfs_fields:
            neighbors = [i for i in dfs_fields[-1].get_neighbors()
                         if i.wayable]
            if neighbors:
                new_field = random.choice(neighbors)
                new_field.wayable = False
                if len(dfs_fields) > 1:
                    if diagonal:
                        if len([i for i in new_field.get_neighbors()
                                if i.type]) > 1:
                            continue
                    elif not new_field.check_field(dfs_fields[-1]):
                        continue
                new_field.type = WAY
                new_field.waylength = len(dfs_fields)
                dfs_fields.append(new_field)
            else:
                dfs_fields.pop()

    def generate_maze_prim_mod(self, start_pos):
        self.generate_maze_prim(start_pos, True)

    def generate_maze_prim(self, start_pos, diagonal=False):
        self.diagonal_walls = diagonal
        self.walls = []
        start = self.start_field(start_pos)
        start.add_walls()
        while self.walls:
            wall = random.choice(self.walls)
            self.walls.remove(wall)
            if diagonal:
                if len([i for i in wall[1].get_neighbors() if i.type]) > 1:
                    continue
            elif not wall[1].check_field(wall[0]):
                continue
            wall[1].type = WAY
            wall[1].add_walls()
            wall[1].waylength = wall[0].waylength + 1